package com.lsa.letcode.the108.sortedArrToBst;

import static org.junit.Assert.assertTrue;

import java.io.IOException;
import java.util.Arrays;

import org.junit.Test;

import com.google.common.primitives.Ints;
import com.lsa.helpers.IntegerComparator;
import com.lsa.iview.trees.BinaryTree.Node;
import com.lsa.iview.trees.BinaryTreeUtils;
import com.lsa.letcode.common.LetCodeTestBase;
import com.lsa.letcode.common.TreeNode;
import com.lsa.letcode.common.TreeUtils;

public class SortedArrToBstTest extends LetCodeTestBase{
	@Test
	public void test() throws Exception {
		test("oneNode.tgf");
		test("test1.tgf");
		test("test2.tgf");
		test(new int[]{1,1,1,2,2,3,3,4,5});
		test(new int[]{1,1,1});
		test(new int[]{1,1});
		test(new int[]{1});
		test(new int[]{1,2,3,4,5,6,7,8,9,9,9,9});
		test(new int[]{1,1,1,2,3,4,5,6,7,8,9});
		test(new int[]{1,1,1,2,3,4,5,6,7,8,9,9,9,9});
		test(new int[]{1,1,1,2,3,4,5,6,7,8,9,9,9});
		test(new int[]{1,2,3,4,4,5,6,7,8,9});
		test(new int[]{1,2,3,4,4,4,5,6,7,8,9});
		int[] arr = new int[1000];
		Arrays.fill(arr, 1);
		test(arr);
	}
	
	private void test(String resName)
			throws IOException {
		TreeNode n = TreeUtils.fromTgf(this.getClass(), resName);
//		System.out.println(BinaryTreeUtils.toString(TreeUtils.copyAdaptTree(n)));
//		System.out.println(TreeUtils.inorder(n));
		test(Ints.toArray(TreeUtils.inorder(n)));
//		System.out.println(BinaryTreeUtils.toString(t2));
//		Assert.assertEquals(expected, actual);
	}

	private void test(int[] inorder) {
		Solution s = new Solution();
		TreeNode bstFromArr = s.sortedArrayToBST(inorder);
		int[] inorder2 = Ints.toArray(TreeUtils.inorder(bstFromArr));
		assertTrue(Arrays.equals(inorder, inorder2));
		Node<Integer> t2 = TreeUtils.copyAdaptTree(bstFromArr);
//		System.out.println("-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=");
//		System.out.println(String.format("<<<< %s >>>>", TreeUtils.maxDepthRec(bstFromArr)));
//		System.out.println(BinaryTreeUtils.toString(t2));
		assertTrue(BinaryTreeUtils.isBst(IntegerComparator.instance(), t2, inorder[0], inorder[inorder.length - 1]));
	}
}
